之前其实写过几篇博客零散的讨论过这个问题，但是要么结论不强，要么证明不优美，这次突发奇想，一下子看穿了二阶的情形。
在之前博客中讲过
$$ |GL(n,p)| = \prod_{i=0}^{n-1} (p^n-p^i) $$
即对任意 $n$ 阶可逆矩阵 $A$， $A^{|GL(n,p)|}=I_n$。
我们通常求 $n$ 阶线性递推关系表示的数列时都是用矩阵来做的，此时的矩阵其实对应着它的有理标准型，是一类特殊的矩阵，因此很有可能，此类矩阵的周期仅仅是 $|GL(n,p)|$ 的一个因子。
二阶线性递推关系数列模素数$p$ 周期为 $p^2-1$
设 $f(n)=af(n-1)+bf(n-2),n \geq 2,f(0),f(1)$ 给定。
设 $x^2-ax-b=0$ 的解为 $x_1,x_2$ 那么
$$ f(n) = c_1 x_1^n + c_2 x_2^n $$ 其中 c_1,c_2 为由 $f(0),f(1)$ 决定的常数。这里 $x_1,x_2 = \frac{a \pm \sqrt{a^2+b}}{2}$
如果我们在$\mod p$ 的意义下处理，问题就变成了求 $g(n)=(a + b \sqrt{d})^n$ 的周期为多少?
我们考虑
$$ F = \lbrace a + b \sqrt{q} \mid 0 \leq a,b<p \rbrace$$
- 若 $q$ 是 $\mod p$ 二次剩余，那么显然 $F=\mathbb{Z}_p$
- 否则，$F$ 是域 $\mathbb{Z}_p$ 的二次拓域。其非0元全体关于乘法构成了群。
因此无论何种情形都有 $g(p^2)=g(1)$。并且我们求解时可以不依赖矩阵，而直接用 $F$ 中的乘法解决。